ガベージコレクション - 自動的メモリ管理を構成する理論と実装
The Garbage Collection Handbookの邦訳
まあまあ難しい
序文
ガベージコレクションはLispの一部として誕生した 1990年代以降に開発された言語で自動的メモリ管理を採用していない言語はほとんどない
2010年の本です
ガベージコレクションを用いると多くのバグが消せる
すでに解放したメモリをもう一度解放してしまう
CPUの性能向上に対してDRAMメモリが遅れをとっている状況は変わっていない コンパイル時解析はあまり触れない
1章
動的なメモリ管理
不要になったオブジェクト(が使っているメモリ)をどう回収するか
明示的解放
Cのfree
C++のdelete
明示的解放で起きるエラー
明示的解放は本質的に難しい
オブジェクトの活性(生きてるか死んでるか)はグローバルな性質であるが、ある変数にfreeするかしないかというのはローカルな決定であるから
明示的解放ではインターフェイスが明示的・暗黙的に複雑化する
ガベージコレクションで解決できる
解放に関する決定はすべてガベージコレクタがやるので二重解放が起きない
グローバルな情報も持っている
コンポーネントのインターフェイスからメモリ管理を切り離すことで再利用性を向上させる
最強のガベージコレクションアルゴリズムは存在しない
そもそも比較が難しい
ガベージコレクションの安全性
生きているオブジェクトを回収してはならない
完全性
ヒープ内のすべてのごみが最終的には回収されるという性質
純粋な参照カウントGCは循環参照を回収できない
毎回のGCサイクルごとにすべてのごみを回収することがパフォーマンス上良いとも限らない
多くのGCはプログラムを時々停止させる
空間的オーバーヘッド
GCを用いるプログラムはミューテータとコレクタの2つに分けられる
ミューテータ
アプリケーションコード
新しいオブジェクトを割り付ける
オブジェクトの参照フィールドが指すオブジェクト(destination)を変更する(mutate)
コレクタ
ガベージコレクションコード
到達不能オブジェクトを発見してメモリ領域を回収する
1つのプログラムに複数のミューテータスレッドが存在してもよい
オブジェクトを指す参照はヒープのオブジェクトに限らない
ルートと呼ばれる場所にもある
static変数
スレッドのスタック
ミューテータによる参照の更新の結果、オブジェクトがどのルートからも到達できなくなったとき、オブジェクトが到達不能であるという
型安全なミューテータは到達不能なオブジェクトにアクセスできない
ランタイムシステムとのやりとりなしには
オブジェクトが生きているということ
オブジェクトがミューテータの実行によってアクセスされること
決定不能
任意のプログラムについて、プログラムがヒープの特定のオブジェクトにアクセスするかどうかを決定する手段はない
オブジェクトの生死の決定不能性は、停止問題の系である
なるほど？
オブジェクトの生死判定の近似として、ポインタの到達可能性(reachability)がある
「オブジェクトNはMから到達可能である」とは
NがMのフィールドfから始まるポインタの連なりをたどって到達できること
ミューテータが型安全という前提の下で、オブジェクトが到達不能であるならばミューテータがオブジェクトを操作することはない 逆に、オブジェクトが到達可能である場合は生きているかもしれない
ここで出てくるのか
マーク…ルート集合から出発してオブジェクトのグラフを走査し、発見したオブジェクトをマークする
スイープ…ヒープ内の全オブジェクトを調べ、マークされていないものをごみとみなして回収する
(最適化は省略)
単純なマークスイープGCではミューテータによる読み書きにまったくオーバーヘッドがない
オブジェクトの移動を行わないのでメモリが断片化する恐れがある
マークコンパクトGC
圧縮…生きたオブジェクトを再配置してヒープを圧縮することで断片化を解消する